#include<iostream>
using namespace std;
int main(){
    int dp[100][100]={0},n,bag,weights[100],value[100];
    cin>>n>>bag;
    for(int i=0;i<n;i++){
        cin>>weights[i]>>value[i];
    }
    for(int j=bag;j>=weights[0];j--) dp[0][j]=value[0];
    for(int i=0;i<n;i++){
        for(int j=1;j<=bag;j++){
            if(weights[i]>j) dp[i][j]=dp[i-1][j];
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+value[i]);
            }
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    
}